
#pragma once

#include <atomic>
#include<memory>
#include<utility>

namespace rocksdb {

    template<typename T, typename... Ts>
    std::unique_ptr<T> make_unique(Ts&&... params)
    {
        return std::unique_ptr<T>(new T(std::forward<Ts>(params)...));
    }
/**
 * A very simple atomic single-linked list primitive.
 *
 * Usage:
 *
 * AtomicLinkedList<MyClass> list;
 * list.insert(a);
 * list.sweep([] (MyClass& c) { doSomething(c); }
 */
    template <class T>
    struct ListHook {
        ListHook(){}
        T data;
        std::atomic<ListHook*> next{nullptr};
    };


    template <class T>
    class AtomicLinkedList {
        ListHook<T> head_;
        std::atomic<size_t> size_{0};
    public:
        AtomicLinkedList() {}
        AtomicLinkedList(const AtomicLinkedList&) = delete;
        AtomicLinkedList& operator=(const AtomicLinkedList&) = delete;
        AtomicLinkedList(AtomicLinkedList&& other) noexcept = default;
        AtomicLinkedList& operator=(AtomicLinkedList&& other) = default;

        ~AtomicLinkedList() {
            ListHook<T> *prev=&head_,*cur, *next;
            cur = prev->next.load();
            while(true){
                if (cur == nullptr){
                    return;
                }
                next = cur->next.load();
                delete cur;
                cur = next;
            }
        }

        bool empty() const { return head_.next == nullptr; }
        size_t size() const {return size_.load();}

        /**
         * Atomically insert t at the head of the list.
         * @return True if the inserted element is the only one in the list
         *         after the call.
         *以原子方式在列表的开头插入t。
         *如果插入的元素是调用后列表中唯一的元素，则返回True。
         */
        bool insertHead(T t) {
            auto cur = new ListHook<T>();
            cur->data = t;
            ListHook<T>* next = nullptr;
            while(true){
                next = head_.next.load();
                cur->next.store(next);
                if (head_.next.compare_exchange_strong(next, cur)){
                    size_.fetch_add(1);
                    return true;
                }
            }
            return false;
        }

        bool insertSorted(T t) {
            auto cur = new ListHook<T>();
            cur->data = t;
            ListHook<T>* next = nullptr, *prev = &head_;
            while(true){
                next = prev->next.load();
                if (next == nullptr || cur->data.compare(next->data) < 0){
                    // 插入两个之间
                    cur->next.store(next);
                    if (prev->next.compare_exchange_strong(next, cur)){
                        size_.fetch_add(1);
                        return true;
                    }else{
                        prev = &head_;
                        continue;
                    }
                }
                prev = next;
                next = next->next.load();
            }
        }

        /**
         * Repeatedly pops element from head,
         * and calls func() on the removed elements in the order from tail to head.
         * Stops when the list is empty.
         * 不断从头部弹出元素，
          *并按从尾到头的顺序对删除的元素调用func（）。
          *列表为空时停止。
         */
        bool sweepHead(T& t) {
            ListHook<T> *prev,*cur, *next;
            while(true){
                prev = &head_;
                cur = prev->next.load();
                if (cur == nullptr){
                    return false;
                }
                next = cur->next.load();
                if (prev->next.compare_exchange_strong(cur, next)){
                    t = cur->data;
                    delete cur;
                    size_.fetch_sub(1);
                    return true;
                }
            }
        }
    };

} // namespace rocksdb
